package puzzle.projecteuler.p300;

import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;
import astudy.util.AdvMath.Factors;


public class Problem248C {

	/**
	 * phi(n) = Π p^(a-1)*(p-1) = m
	 * 算法出发点相对简单：找到13!的所有形如p^(a-1)*(p-1)的因子。
	 * 
	 * phi(n)是积性函数. 所以,如果n = n1*n2, gcd(n1, n2) = 1, 就有phi(n) = phi(n1) * phi(n2) 
	 * 只要将m = phi(n)分成两部分 m1 * m2, 如果存在n1, n2 满足:
	 * 1) gcd(n1, n2) = 1
	 * 2) phi(n1) = m1, phi(n2) = m2
	 * 那么n = n1*n2就是一个解。 
	 * 
	 * anwser	: 
	 * time cost:  ms
	 * @param args
	 */
	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();
		long count = 0;
		Factors m = getM();
		List<Factors> factors = m.getAllFactors();
		List<Factors> validFactors = new ArrayList<Factors>();
		for (Factors factor: factors) {
			validFactors.addAll(check(factor.longValue()));
		}
		for (Factors f: validFactors) {
			System.out.println(f);
		}
		System.out.println(validFactors.size());
		System.out.println(count);
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
	
//	/**
//	 * 返回所有满足phi(n)=m的n
//	 * @param m
//	 * @return
//	 */
//	public static List<Factors> find(Factors m) {
//		
//		List<Factors> ns = new ArrayList<Factors>();
//		if (m.longValue() == 1) {
//			ns.add(new Factors(2));
//		} else {
//			List<Factors> factors = m.getAllFactors();
//			for (Factors m1: factors) {
//				Factors m2 = m.divide(m1);
//				if (m1.longValue() != 1L && m2.longValue() != 1L) {
//					List<Factors> n1s = find(m1);
//					List<Factors> n2s = find(m2);
//					for (Factors n1: n1s) {
//						for (Factors n2: n2s) {
//							if (n1.gcd(n2).longValue() == 1L) {
//								ns.add(n1.multiply(n2));
//							}
//						}
//					}
//				}
//			}
//		}
//		return ns;
//	}
	
	public static Factors getM() {
		
		//13! = 2^10 * 3^5 * 5^2 * 7 * 11 * 13
		Factors factors = new Factors();
		factors.put(2L, 10);
		factors.put(3L, 5);
		factors.put(5L, 2);
		factors.put(7L, 1);
		factors.put(11L, 1);
		factors.put(13L, 1);
		return factors;
	}
	
	/**
	 * 判断t是否是下面类型的一种：
	 * p-1, 2^a, 3^a*2, 5^a*4, 7^a*6, 11^a*10, 13^a*12
	 * 并返回所有的可能
	 */
	public static List<Factors> check(long t) {
		
		List<Factors> fs = new ArrayList<Factors>();
		if (AdvMath.isPrime(t+1)) {
			Factors f = new Factors();
			f.put(t+1, 1);
			fs.add(f);
		}
		
		Integer pow = null;
		//2^a
		pow = powerOf(t,2);
		if (pow != null) {
			Factors f = new Factors();
			f.put(2L, pow);
			fs.add(f);
		}
		//3^a*2
		if (t % 2 == 0) {
			long x = t/2;
			pow = powerOf(x,3);
			if (pow != null) {
				Factors f = new Factors();
				f.put(2L, 1);
				f.put(3L, pow);
				fs.add(f);
			}
		}
		//5^a*4
		if (t % 4 == 0) {
			long x = t/4;
			pow = powerOf(x,5);
			if (pow != null) {
				Factors f = new Factors();
				f.put(2L, 2);
				f.put(5L, pow);
				fs.add(f);
			}
		}
		//7^a*6
		if (t % 6 == 0) {
			long x = t/6;
			pow = powerOf(x,7);
			if (pow != null) {
				Factors f = new Factors();
				f.put(2L, 1);
				f.put(3L, 1);
				f.put(7L, pow);
				fs.add(f);
			}
		}
		//11^a*10
		if (t % 10 == 0) {
			long x = t/10;
			pow = powerOf(x,11);
			if (pow != null) {
				Factors f = new Factors();
				f.put(2L, 1);
				f.put(5L, 1);
				f.put(11L, pow);
				fs.add(f);
			}
		}
		//13^a*12
		if (t % 12 == 0) {
			long x = t/12;
			pow = powerOf(x,13);
			if (pow != null) {
				Factors f = new Factors();
				f.put(2L, 2);
				f.put(3L, 1);
				f.put(13L, pow);
				fs.add(f);
			}
		}
		return fs;
	}
	
	public static Integer powerOf(long t, int p) {
		
		int pow = 0;
		while (t%p == 0) {
			t /= p;
			pow ++;
		}
		if (t == 1) {
			return pow;
		} else {
			return null;
		}
	}
}
